1. Field of the Invention
The present invention relates to a single instruction, multiple data stream parallel computer.
2. Description of the Prior Art
The history of the development of digital computers is replete with examples of attempts to maximize operating speed, i.e., the amount of data that can be processed in a unit of time. The two important limitations on the developments of this area concern the component speed and the serial machine organization. Improvements in the area of integration have provided for a possibility of increased operating speed while the improvements concerning the serial machine organization have been directly tied to improvements in the execution times of serial instruction strings.
Functional features such as index registers, associative memories, instruction look-ahead, high-speed arithmetic, algorithms, and operand look-ahead have been employed to expedite extension of the instruction strings. This type of "pipe-lining" of computers has reached a practical limitation in the application of these features. An example of this "pipe-line" is the CRAY-1.
Other examples of machines presently available which attempt to utilize the most recent developments in parallel processing include the DAP, STARAN, and the massively parallel processors (MPP), which use bit-serial communications between processing elements arranged in a large array as a communications network. These machines are distinguished from each other and from other machines by their powerful processing elements (PE), the amount of memory per processing element, and their intercommunication network.
One of the problem areas with regard to these machines is that any work being done on arrays greater than 2.sup.12 element causes the speed of execution to be constrained by the communication network. That is, the DAP, STARAN, and MPP are limited in algorithms whose communication paths can be mapped onto a rectangular grid.
It has been recognized by Pratt in "A Characterization of the Power of Vector Machines," Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, Seattle, Wash., Apr. 30-May 2, 1972, pp. 122-134, that a "new" model of the random access machine called a Boolean vector machine could be used to provide for bitwise parallel Boolean operations. Their theoretical discussion indicated that Boolean vector machines of unlimited register length could solve all problems in NP in time polynomial in the problem sized. (NP is the class of language recognition problem solvable by non-deterministic Touring machine in polynomial time). The class NP includes problems for which deterministic polynomial-time solutions have long been sought without success. The revelations of Pratt indicated that a vector machine model could solve in time t.sup.2 any problem solvable by Touring machine in space t.
This theoretical construction of a vector machine by Pratt did not provide for any finite realizations of Boolean vector machine and certainly not any architecture which was able to accomplish the theoretical results.
Thus, there has been no architectural realization of the indicated possibilities with regard to providing a Boolean vector machine able to utilize any of the principles set forth by Pratt.